As a procedure call is a basic computing paradigm in a procedural language, a message sending is a basic computing paradigm in an object oriented language. Accordingly, to efficiently implement message sending is indispensable for efficiently implementing an object oriented language. However, in an object oriented language, a method invoked in the execution of a message sending varies depending on the class of the receiver object, and cannot be determined at compilation time. This is called dynamic binding of the method, and a task called a method lookup must be carried out at run time. Thus, the processing of message sending becomes heavy and produces a bottleneck in the execution performance.
A method lookup is to locate a method to be executed from a pair of a class (type) of a receiver object and a selector (the name of a method). One useful implementation method for method lookup is a dispatch table method. The basic idea of this method is that a method lookup is performed "in advance" for the possible combinations of classes and selectors and the results are stored in an array called a dispatch table, and the cost of the method lookup is the cost of the array reference.
Specifically, numbers are assigned to selectors, and a dispatch table is created for each class. For each selector s which a certain class C can understand, the corresponding method is looked up, and its address is stored in the entry of the CODE(s) in the dispatch table of the class C (CODE is a mapping from a selector set to a positive integer, and represents the numbering of selectors). For example, the address is stored in the header of an object so that the dispatch table is easily traced from the object. With this, an instruction in a high-level language for instructing the execution of a message sending substantially becomes the following pseudo C code.
(*receiver.fwdarw.dispatchTable[CODE(selector)])(receiver, arg1, arg2, . . . );
Thus, the method lookup results in array reference, and the cost of the message sending decreases to the cost of the array reference and indirect procedure call. This is equivalent to the cost of calling the virtual function of C**.
In a simple dispatch table method, a CODE function is used in which unique numbers are assigned to all the selectors. A class hierarchy as in FIG. 11 is taken by way of example. There are six different selectors as a whole, and eight methods are defined in four classes. In FIG. 11, on the right to the node corresponding to a class, the selectors of the method defined in that class are written. FIG. 12 shows an example of the dispatch tables and the numbering of selectors in the simple method which are created in the case of a class hierarchy such as in FIG. 11.
Taking the memory efficiency of the simple method, dispatch tables having a size of the number of selectors exist by the number of classes. If the size of an entry of a dispatch table is assumed to be four bytes, the memory consumption of the example of FIG. 11 is 6.times.4.times.4 bytes=96 bytes. Although it seems that the example of FIG. 11 has no problem with the simple method, it is not practical in view of the memory consumption as shown by Table 1 if applied to a vast commercial system.
TABLE 1 ______________________________________ Memory efficiency Number of Number of Consumption Filling System classes selectors (byte) rate (%) ______________________________________ A 1,356 10,051 54M 4.5 B 3,241 17,342 255M 1.0 C 1,956 13,474 80M 2.3 ______________________________________
A dispatch table is a so-called sparse array when applied to a large system such as a commercial system, and most of the entries are not used. That is, one class cannot understand all the selectors existing in a system, but can understand only a small subset of them. Accordingly, as shown in Table 1, the filling rate, namely, the proportion of the "memory consumption of the entries which are not empty" to the "memory consumption of a dispatch table" is several percent, which is very low.
In view of the foregoing, memory efficiency is subject to improvement, and several methods are actually proposed. Typical compression methods, such as row displacement and selector coloring are known.
The concept of the row displacement is that a plurality of sparse arrays are packed into one long array. For instance, the dispatch table in FIG. 12 are packed as shown in FIG. 13. The "Row displacement (for each class)" column in Table 2 shows the filling rate when the described simple method is applied to a commercial system and compression is performed by the row displacement.
TABLE 2 ______________________________________ Filling Rate (%) Selector Row displacement Row displacement coloring (for each System (for each class) (upper limit) selector) ______________________________________ A 50 42 99.8 B 55 43 99.7 C 55 57 99.7 ______________________________________
Selector coloring is based in the view that unique numbers need not be assigned to all the selectors. If two selectors are understood by the same class, it is said that the two selectors conflict, but it is only needed to assign a different number insofar as they conflict. The specific sequence of performing the numbering can be reduced to the so-called graph coloring problem. That is, the problem that a graph obtained by making nodes from selectors and drawing arcs between the conflicting selectors is colored with as small a number of colors as possible. The number assigned to a selector in this way is called the color or color number of the selector. An example of the coloring for the selectors in FIG. 11 and the dispatch tables formed according to it are shown in FIG. 14. (This coloring is actually optimal.)
In selector coloring, the size of a dispatch table is equal to the number of colors. And, the optimal number of colors is not smaller than the number of selectors which one class can understand. From this, the lower limit of the memory consumption and the upper limit of the filling rate can be determined. The limit of the filling rate is shown in the "Selector coloring (upper limit)" column in Table 2.
On the other hand, row displacement has a variation that can be called a change of concept. That is to assign numbers to classes and make a dispatch table for each selector, rather than to assign numbers to selectors and make a dispatch table for each class. The completed dispatch tables are also packed into one long array. As shown in the "Row displacement (for each selector)" column in Table 2, the filling rate increases to nearly 100% if this variation is applied to a commercial system. The reason for this is that the algorithm for packing used in the row displacement prefers many short arrays to a few long arrays. As apparent from the comparison between the number of classes and the number of selectors in Table 1, many short arrays are created if a dispatch table is made for each selector.
Three compression methods have been described above, but the problem with the dispatch table is that memory efficiency is not satisfactory even if the filling rate is 100%. Memory efficiency for a filling rate of 100% is shown in Table 3. If as a result the virtual image is increased by 50%, or it is not practical. (Smalltalk includes a virtual machine controlling the whole system in cooperation with hardware, and a virtual image including application programs and the like.)
TABLE 3 ______________________________________ Filling rate of 100% Size of Ratio to virtual image Memory consumption virtual image System (M bytes) (M bytes) (%) ______________________________________ A 3.81 3.10 81 B 7.12 7.69 108 C 4.77 2.47 52 ______________________________________
What is, the dispatch table method is excellent as an implementation method for message sending in the point of time efficiency, but still has problems with memory efficiency and it not considered to be practical.
To clarify the difference between the subject invention described below and background art, a problem in the use of a compression technique for the dispatch table method is described.
A phenomenon called selector mismatch occurs if row displacement or selector coloring is used, requiring action to be taken. Selector mismatch is described by an example of selector coloring. First, a message sending expression "aNumber quo: 7" is taken, which means that the message of a selector called quo: is sent to an object called aNumber with an argument of 7. If selector coloring is provided as shown in FIG. 14, the result of the compilation of this message sending expression is given as the following pseudo C code.
//The color number of quo is 3.
(*aNumber.fwdarw.dispatchTable[3])(aNumber,7)
If the variable aNumber "erroneously" points to a Collection object, the method of the do: selector is invoked even though the quo: selector cannot be understood in the Collection class. This is the selector mismatch phenomenon, which of course should not be overlooked. Countermeasures should be taken such as a technique of card number matching may be used. First, a unique number called a card number is assigned to each selector in addition to the color number, and the card number of the selector of a method is stored in the method. And, if a message sending occurs, the "card number of the selector in the message sending expression" is compared with the "card number of the selector of the method to be invoked." If card number matching is used, the result of the compilation of the above message sending expression is expressed by the following psuedo C code.
______________________________________ //the color number of quo: is 3, and the card number is 26. method = aNumber-&gt;dispatchTable[3]; if (method-&gt;selectorCard = = 26) (*method)(aNumber,7) else SelectorMismatchHandler(. . .); ______________________________________
The maintenance and management of the card number is not so expensive. For instance, it is possible that all the selectors are registered in a hash table called a selector table, and the index of this table is used as the card number. The size of the selector table is sufficient if it is about two times the number of the selectors.
The above described selector mismatch handler SelectorMismatchHandler generates an exception DoesNotUnderstand. However, no selector mismatch occurs unless a different object is indicated or some error occurs.
Further, a method close to the above described simple method is described in Published Unexamined Patent application No. 5-20082. Moreover, a description on limiting the number of the entries of a table used for message sending is contained in Published Unexamined Patent Application No. 6-214884.
However, such references do not describe a method for increasing memory efficiency while maintaining the time efficiency of the dispatch table method described above.
Accordingly, an object of the present invention is to provide a method for increasing the memory efficiency in an object oriented program while maintaining the time efficiency of the dispatch table method.